II. Field of the Invention
The present invention relates to communications. More particularly, the present invention relates to a novel and improved method for registration of a mobile communications device in a cellular communications environment.
III. Description of the Related Art
In a cellular communication system registration is the process a mobile station uses to notify a cellular communication system whether it is on the air and which base station it is receiving. The mobile station may be of a cellular radiotelephone or personal communication device typically in the form of a vehicle mounted unit or a hand carried portable unit. For calls that are directed towards a mobile station, the cellular system uses the registration information to reduce the amount of paging by determining whether to page a mobile station and, if so, by determining the set of base stations in which to broadcast the page.
For calls directed to a mobile station, often called mobile terminated calls, the land system must determine whether the mobile station is powered on and which base station the mobile station is receiving. To find the mobile station, the cellular system broadcasts a message, often called a page, from many base stations. If the mobile station responds, the cellular system continues handling the call with further communication being directed to the base station of the coverage area in which the mobile station is located. It should be further understood that the paging process is used to locate the mobile station for any other transaction to be done with the mobile station. The base station and its coverage area are commonly referred to as a cell.
If the system has no knowledge of the location of the mobile station, then the system must broadcast pages in every sector of every base station. As the amount of mobile terminated traffic increases, the communications resources to support system wide paging quickly becomes enormous in most large metropolitan areas.
A mobile station uses a process called registration to inform the cellular system where the mobile station is located. Well known methods of registration in the art include registration at power up, and registration upon entering each new base station coverage area, among many others. Several systems, such as AMPS and GSM, use a periodic or counter method to determine the location of the mobile station. The counter method is similar to the timer method described herein. Although these methods are far from ideal, they nevertheless can significantly reduce the amount of required paging.
An analysis of the timer method assumes the uniform hexagonal tessellation of the plane or uniform circular base station coverage areas with radius r.sub.c. The same expected number of mobile stations, given by N.sub.a, is assumed to be in every base station coverage area.
In a cellular system implementing the timer method each mobile station registers every T.sub.r seconds. This requirement can be easily implemented by having the mobile station increment a counter periodically, or increment a counter in response to a global command from the system. By either supplying the maximum value of the counter or varying the increment rate, the system can vary T.sub.r. The average registration message rate, .lambda..sub.reg, per base station is thus given by the following equation: ##EQU1##
For a mobile terminated call, the system needs to determine the set of base station coverage areas that the mobile station may have entered. If the mobile station can move at some maximum velocity v.sub.m, then the distance that the mobile station could have traveled is v.sub.m (t-t.sub.r) where t.sub.r is the time when the mobile station last registered. Unless the system knows where in the base station coverage area the mobile station was located when it registered, the system must assume that the mobile station was on the coverage area boundary. Unless the system has some direction information, it must assume that the mobile station was moving outward.
For a randomly chosen mobile station, the expected number of base stations that must page can readily be found. The elapsed time since registration is a uniformly distributed random variable on [0, T.sub.r ]. Rather than considering the exact result which is discontinuous in the distance, more insight can be obtained by considering a quadratic approximation to the number of base stations as function of the distance. The expected number of base stations that the mobile station must be paged in, M.sub.s, is in accordance with the equation: ##EQU2##
The quantity r.sub.c /vm is the time that a mobile station moving at velocity v.sub.m takes to move from the center of a coverage area to its boundary. If the excess outbound message rate is defined as the expected number of pages other than the answered page plus the expected number of messages that must be sent to acknowledge registrations, then the excess outbound message rate, .lambda..sub.ex, is determined by the equation: ##EQU3## where: M.sub.p is the number of times that a page message is repeated; p.sub.p is the probability that the page is answered by the mobile station on a particular page repetition; and
N.sub.a .lambda..sub.m .alpha..sub.t is the origination rate for mobile terminated calls in a base station coverage area. PA1 new lat and new long are respectively the latitude and longitude in degrees of the base station of the coverage area in which the mobile station is located; and PA1 registered lat and registered long are respectively the latitude and longitude in degrees of the base station in which the mobile station last registered.
As the interval between registrations, T.sub.r, decreases, the number of base stations that must page decreases, but the acknowledgment rate increases. Thus some value of T.sub.r minimizes .lambda..sub.ex.
The main problem with the timer method is that paging must be done in an area commensurate with the maximum vehicle velocity. If the region has a few routes that allow high velocity, then the system must use the highest velocity route for determining where to page. Portable units, which normally don't move very fast, may nevertheless be in a fast moving vehicle and cannot be counted as a separate class. Techniques which begin paging in a small region and then expand the paging region if the mobile station does not respond can be used to reduce the amount of paging at the expense of delay.
Another registration technique known as the zone based method is also used to reduce the amount of paging in a cellular system. The zone based method may simply divide the system into regions called zones. Thus, base stations are grouped together to form fixed paging zones. Upon registration in a zone, the mobile station is paged from all base stations within the zone. The mobile station typically maintains a list of zones that it has recently visited. If the mobile station enters a zone not on the list, it then registers. Therefore as the mobile station travels throughout the system, it registers each time it travels into a new zone.
A variation of the basic zone based method is described in the article entitled "A New Location Updating Method for Digital Cellular Systems," by Okasaka, Sadaatsu, Onoe, Seizo, Yasuda, Syuji, and Maebara, Akihiro, Proceedings of the 41st IEEE Vehicular Technology Conference, St. Louis, Mo., May 19-22, 1991, pp. 345-350. In this variation of the zone based method, layers of zones are created along with the group of mobile stations divided by parameters, such as mobile station serial number, into which layer of zones the mobile station will register.
An analysis of the zone based method again assumes the uniform hexagonal tessellation of the plane or uniform circular base station coverage areas with radius r.sub.c. The same expected number of mobile stations, again given by N.sub.a, is assumed to be in every base station coverage area.
As mentioned above, in the zone based method every coverage area in a system is assigned to a specific fixed zone. Every base station broadcasts the zone to which it is assigned. The mobile station keeps a list of zones that it has recently visited. Whenever a mobile station enters a zone not on its list, the mobile station registers and adds the zone to the list.
Vehicular traffic theory can used to estimate the expected peak registration rate for a perimeter base station coverage area. If the coverage area is dominated by one or two main roadways, the rate is relatively easy to compute; otherwise, the computation can be quite tedious. A well known result is that the maximum capacity per lane of traffic on a well designed freeway is about 2000 vehicles per hour and occurs with vehicles moving about 50 km/hour. Good rule of thumb adjustments have been developed for other roadways. If the fraction of vehicles equipped with cellular telephones is known, then the expected peak registration rate can be obtained. For example, if 25% of the vehicles traveling on an 8 lane freeway were equipped with cellular telephones, then the expected peak registration rate for a perimeter base station would be 0.56 registrations per second.
One shortcoming of the zone based method arises in the case of where a heavily traveled route, such as a freeway, intersects a zone boundary. In this instance, all mobile stations register in the base station coverage areas on the zone boundary through which the freeway passes. This situation can place a severe loading on the resources of these particular base stations. One attempt to resolve this problem is to create a staggered or layered zone arrangement as mentioned above. In the fixed staggered zone arrangement, overlapping zones are created in which the particular zone a mobile station registers in is also a function of a serial or identification number of the mobile station. Such a scheme adds a further level of complexity and may not adequately distribute registrations amongst the base stations. It also does not create the hard boundaries necessary between areas administrated by different entities.
A third registration technique known as the distance based method is used to further reduce the amount of paging in a cellular system. The mobile station registers when the distance between the current base station and the base station in which it last registered exceeds a threshold. The mobile station computes a distance measure based on the difference in latitude and longitude between the current base station and the base station where the mobile station last registered. If this distance measure exceeds the threshold value, the mobile station registers with the current base station.
While there are several ways to mechanize this method, a simple way that gives sufficient accuracy has all base stations broadcast latitude (lat), longitude (long), and distance (d.sub.r) parameters. The mobile station registers whenever: ##EQU4## where: d.sub.r is the distance parameter transmitted by the base station in which the mobile station last registered.
Furthermore, EQU .DELTA.lat=new lat-registered lat; and (5) EQU .DELTA.long=(new long-registered long)cos(.pi./180 registered lat); (6)
where:
It should be noted that in equation (6) the cosine factor compensates for the merging lines of longitude as the latitude increases. A more basic approximation of the distance can be achieved be eliminating the cosine factor from equation (6). However without the cosine factor the approximation becomes more inaccurate as the latitude increases. It should be further understood that the distance parameter d.sub.r is typically supplied by the base station where the mobile station last registered. However, in the alternative the distance parameter may be a fixed value stored at the mobile station. It should be further understood that although equations (4)-(6) relate to registrations during the travels of the mobile station, the mobile station also typically registers upon an initial power-up in the system.
The difference between the values (new long) and (registered long), and the difference between the values (new lat) and (registered lat) are respectively typically small for a cellular communications system. Consequently, the approximation set forth by equations (4)-(6) is quite accurate. Errors are less than 1% compared to an exact method, described below, for base station separations up to 200 miles.
In addition, the trigonometric function in equation (4) can be easily approximated by a table lookup function. The square root of the sum of the squares can be approximated by any of several well known approximation methods. One such approximation is: EQU x=max (.vertline..DELTA.lat.vertline., .vertline..DELTA.long.vertline.); and (7) EQU y=min(.vertline..DELTA.lat.vertline., .vertline..DELTA.long.vertline.) (8)
where: ##EQU5## The approximation of equations (7)-(10) supplies a peak error of less than 3% and average RMS errors of about 1%. The approximation can be computed quickly by using shifts, adds, subtractions, and compares in a microprocessor. Other approximations can supply greater (or less) accuracy with additional (or less) computation.
A 64 entry table lookup for the cosine function in equation (6) plus the approximation in equations (7)-(10) to the square root of the sum of the squares for equation (4) gives errors less than 6% for base station latitudes of less than 60 degrees.
As mentioned above, the use of equations (4)-(10) are an approximation to the exact method of computing distance between base stations. An exact method of computing distance for a circular earth model can be defined by the following equations (11)-(16). The exact distance method has the mobile station register again if: EQU d.sub.r .ltoreq.distance (11)
where: ##EQU6## In the above equations (4)-(16) the parameters new long, new lat, registered long and registered lat, are given in degrees. Further information on distance based registration is disclosed in a co-pending U.S. patent application Ser. No. 07/763,091, entitled "MOBILE COMMUNICATIONS DEVISE REGISTRATION METHOD," filed Sep. 20, 1991, and assigned to the Assignee of the present invention, cited above.
For purposes of analysis of the distance method, a homogeneous network of base stations coverage areas such as illustrated in FIG. 3 is considered. Assuming homogeneous vehicle movement in the network, semi-Markov techniques can be used to determine the expected registration rate. While movement from coverage area to coverage area is ordinarily a very complicated stochastic process, a simple model can be obtained by assuming a first order Markov chain with the mobile station entering any of the surrounding base station coverage areas with probability equal to 1/6.
As described in further detail in the above mentioned co-pending application, the registration rate for the distance method tends to be less than for the zone method. A lower excess outbound rate is realized for the distance method because a circular region, or "floating zone," is built around the base station where the mobile station last registered.
With the zone method, the mobile station has a shorter expected distance to traverse before entering a new zone if it registers in a perimeter base station. In practice, there are multiple zones on a zone list. A zone list comprising multiple zones is employed so that the mobile station does not register multiple times as it flips between base stations along the zone boundary. Consequently, the system may have to page the mobile station in multiple zones. This results in the distance method being even more favorable when vehicular traffic follows the above discussed model.
In the zone method, the perimeter base stations of a zone have high registration rates while interior base stations have low registration rates. This can lead to an imbalance in the capacity of the base stations. By having multiple groups of mobile stations and staggering zones relative to each other for each group, the registration rate can be made more homogeneous in the network. However, this defeats the often desirable property of having a well defined zone boundary. Assuming a homogeneous network, the distance method has equal registration rates in all base stations. This will not strictly hold in most networks as mobile stations will tend to initialize registration in certain base stations.
Although the distance based method does provide an improvement over zone and timer registration methods in that there is a reduction in the number of pages transmitted by the base stations, it does not provide by itself a thorough registration scheme upon which a complex operating cellular system can be solely based. Therefore the present invention discloses a comprehensive registration method to reduce paging incorporating the three methods mentioned above with several other discrete registration methods providing a complete, reliable, and realizable scheme.
It is therefore an object of the present invention to provide in a cellular communication system a method by which mobile station pages may be reduced.
It is yet another object of the present invention to provide in a cellular communication system a comprehensive registration scheme which provides a complete and reliable paging mechanism.
It is yet a third object of the present invention to provide in a cellular communication system a comprehensive mobile station registration method by incorporating several discrete methods of registration into a complete registration scheme.